package class_4;

import java.util.Arrays;
import java.util.Random;

public class Coding_DecodewaysII {
	public static int numDecodings(String str) {
		if(str==null || str.length()<1) {
			return 0;
		}
		return f(str.toCharArray(), 0);
	}
	
	public static int f(char[] s, int cur) {
		if(cur==s.length) {
			return 1;
		}
		if(s[cur]=='0') {
			return 0;
		}
		int ans = f(s,cur+1) * (s[cur]=='*'? 9: 1);
		if(cur + 1 < s.length) {
			if(s[cur]!='*') {
				if(s[cur+1]!='*') {
					if((s[cur]-'0') * 10 + s[cur+1] - '0' <= 26) {
						ans += f(s, cur+2);
					}
				}
				else {
					//s[cur+1]=='*'
					switch (s[cur]) {
					case '1':
						ans += 9 * f(s,cur+2);
						break;
					case '2' :
						ans += 6 * f(s,cur+2);
						break;
					default :
						break;
					}
				}
			}
			else {
				//s[cur]=='*'
				if(s[cur+1]!='*') {
					ans += f(s, cur+2);//when s[cur]转化为'1'时， 至少可以获得一份
					if(s[cur+1]>'0' && s[cur+1]<='6') {
						// when s[cur]转化为'2'时，看s[cur+1]是否在范围内。
						ans += f(s, cur+2);
					}
				}
				else {
					//s[cur+1]=='*'
					
					//when s[cur]=='1' ,9 cases
					//when s[cur]=='2' ,6 cases
					ans += 15 * f(s, cur+2);
				}
				
			}
		
		}
		return ans;
	}
	///------------------------------------------
	
	public static long mod = 1000000007;
	/**
	 * 动态规划法
	 */
	public static int numDecodings1(String str) {
		if(str==null || str.length()<1) {
			return 0;
		}
		int[] dp = new int[str.length()];
		Arrays.fill(dp, -1);
		return (int)f1(str.toCharArray(), 0, dp);
	}
	public static long f1(char[] s, int cur, int[] dp) {
		if(cur==s.length) {
			return 1;
		}
		if(dp[cur]!=-1) {
			return dp[cur];
		}
		long ans = 0L;
		if(s[cur]=='0') {
			dp[cur] = 0;
			return ans;
		}
		
		ans += f1(s, cur+1, dp) * (s[cur]=='*'?9:1);
		if(cur + 1 < s.length) {
			if(s[cur]!='*') {
				if(s[cur+1]!='*') {
					if(((s[cur]-'0') * 10 + (s[cur+1] - '0')) <= 26) {
						ans += f1(s, cur+2, dp);
					}
					//不满足则退出分支讨论。
				}
				else {
					//s[cur+1]=='*'
					switch(s[cur]) {
					case '1':
						ans += 9 * f1(s, cur+2, dp);
						break;
					case '2':
						ans += 6 * f1(s, cur+2, dp);
					default :
						break;
					}
				}
			}
			else {
				// s[cur] == '*'
				if(s[cur+1]!='*') {
					ans += f1(s, cur+2, dp);
					if(s[cur+1]<='6') {
						ans += f1(s, cur+2, dp);
					}
				}
				else {
					ans += 15 * f1(s, cur+2, dp);
				}
			}
		}
		ans %= mod;
		dp[cur] = (int)ans;
		return ans;
	}
	public static int MAX = 100;
	public static char[] ch = new char[MAX];
	public static long random() {
		return (long)(Math.random() * 10);
	}
	public static void main(String[] args) {
		Random random = new Random();
		int n = random.nextInt(MAX);
		int num = 0;
		for(int i=0;i<n;i++) {
			num = random.nextInt(11);
			if(num==10) {
				ch[i] = '*';
			}
			else {
				ch[i] = (char)(num + '0');
			}
		}
		String s = new String(ch,0,n);
	    System.out.println("字符串长度: " + n);
		 // 为了避免打印过长的字符串，截断显示部分内容
        if (n > 50) {
            System.out.println("字符串: " + s.substring(0, 50) + "...");
        } else {
            System.out.println("字符串: " + s);
        }

        // 暴力递归方式计算解码方案
        long start = System.nanoTime();
        int ret = numDecodings(s);
        long end = System.nanoTime();
        System.out.println("解码方案数 (暴力递归): " + ret);
        System.out.println("暴力递归耗时: " + (end - start) + " 纳秒");
        
        // 带缓存表的dp方式计算解码方案
        start = System.nanoTime();
        ret = numDecodings(s);
        end = System.nanoTime();
        System.out.println("解码方案数 (动态规划): " + ret);
        System.out.println("动态规划（自顶向下）耗时: " + (end - start) + " 纳秒");
	}
}
